package algorithm.leetcode

object PaintBlackGrid {

    fun calcStage(n : Int) : Int{
        var a = 1
        var x = n
        while (x > 0){
            a *= x
            x--
        }
        return a
    }

    fun calc(n : Int, m : Int): Int{
        if(m == 0) return 1
        return calcStage(n) / (calcStage(m) * calcStage(n-m))
    }

    /** 方阵 3, 5, 6, 9
     *  #  #  #  #  #  #
     *  #  #  #  #  #  #
     *  #  #  #  #  #  #
     *  #  #  #  #  #  #
     *  #  #  #  #  #  #
     *  #  #  #  #  #  #
     *  设i行j列
     *  k = i * n + j * (n-i)
     */
    fun paintingPlan(n: Int, k: Int): Int {
        val count = n * n
        if(k == count || k == 0) return 1
        if(k < n || k > count) return 0
        if(k == n) return n*2
//        val facTable = IntArray(n+1)
//        facTable[0] = 1
//        for (i in 1..n){
//            facTable[i] = facTable[i-1] * i
//        }
        var ct = 0
        for (i in 0 until n){
            val j = (k.toFloat() - i*n) / (n-i)
            if(j == 0f || (j >0 && (j / j.toInt() == 1f))){
                println("找到方案，行数为$i, 列数为${j.toInt()}")
                ct += (calc(n, i) * calc(n, j.toInt()))
            }
        }
        return ct
    }
}

fun main() {
//    println(PaintBlackGrid.calc(4, 1) * PaintBlackGrid.calc(4, 3))
    println(PaintBlackGrid.paintingPlan(5, 20))
}